package com.gwcloud.leetcode.hot100;

import java.util.HashMap;
import java.util.Map;

/** 
* @ClassName   : Leetcode169 
* @author      : ganwei 
* @date        : 2020年4月30日 
* @Description : leetcode 169 多数元素 
*/
public class Leetcode0169 {
	/**
	 * - 采用HashMap解决
	 */
    public static int majorityElement(int[] nums) {
    	int length = nums.length;
    	Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    	for(int i = 0; i < nums.length; i++) {
    		Integer value = map.get(nums[i]);
    		if(value != null) {
    			map.put(nums[i], value + 1);
    		}else {
    			map.put(nums[i], 1);
    		}
    	}
    	
    	for(Map.Entry<Integer, Integer> entry : map.entrySet()){
    		Integer k = entry.getKey();
    		Integer v = entry.getValue();
    		if(v > length/2) {
    			return k;
    		}
    	    
    	}
    	
    	return 0;
    }
    
    /**
     * -Boyer-Moore 投票算法 计算复杂度O(N)
     */
    public static int majorityElement_1(int[] nums) {
    	int count = 0;
    	int candidate = 0;
    	for(int num : nums) {
    		if(count == 0) {
    			candidate = num;
    		}
    		count = (num == candidate ? count+1 : count -1);
    	}
    	return candidate;

    }
    
    public static void main(String args[]) {
    	int[] nums =  {2,2,1,1,1,2,2};
    	System.out.println(majorityElement_1(nums));
    }
}
